#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-13 4:43 下午
# @Author  : yangdy
# @File    : 2020-10-11.416.分割等和子集
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = 0
        for x in nums:
            total += x
        if total % 2 == 1:
            return False
        state = [0 for i in range(total//2+1)]
        state[0] = 1
        for x in nums:
            for i in range(total//2, -1, -1):
                if state[i] == 1 and i + x <= total//2:
                    state[i+x] = 1
        return state[total//2] == 1

